/*
 * Created by guoyh on Mon Dec 19 2022 21:38:28
 * leetcode NO.147, https://leetcode.cn/problems/insertion-sort-list/ 
 */
#include <iostream>
#include <gtest/gtest.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if(!head || !head->next) return head;

        // 原链表上排序，不需要额外空间
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode* last = head;
        ListNode* cur = head->next;
        ListNode* tempHead = dummy;
        while(cur){
            // 遍历链表
            if(cur->val >= last->val){
                // 不需要调整顺序
                cur = cur->next;
                last = last->next;
                continue;
            }
            // 遍历每个节点都需要重置 tempHead
            tempHead = dummy;
            //需要调整；找到要插入的位置
            while(tempHead->next->val <= cur->val){
                tempHead = tempHead->next;
            }
            // 一下节点调整逻辑需要结合示意图来理解
            last->next = cur->next;
            cur->next = tempHead->next;
            tempHead->next = cur;
            cur = last->next;

        }
        return dummy->next;


    }

  
};


// 尾插法创建链表
ListNode* build_linklist(vector<int> v){
    ListNode* dummy = new ListNode();
    ListNode* tail = dummy;
    for(int i : v){
        ListNode* newNode = new ListNode(i);
        newNode->next = nullptr;
        tail->next = newNode;
        tail = tail->next;
    }
    return dummy->next;
}


void print(ListNode* l){
    while(l){
        cout<<l->val<<",";
        l = l->next;
    }
    cout<<endl;
}



int add(int a, int b) {
    return a + b;
}

TEST(MyTest, AddTest) {
    vector<int> v = {-1,5,3,4,0};
    ListNode* input = build_linklist(v);
    Solution slu ;
    ListNode* res = slu.insertionSortList(input);
    print(res);

    EXPECT_EQ(res->val, -1);
}

TEST(MyTest, AddTest2) {
    vector<int> v = {-1,5,3,4,0,6};
    ListNode* input = build_linklist(v);
    Solution slu ;
    ListNode* res = slu.insertionSortList(input);
    print(res);

    EXPECT_EQ(res->val, -1);
}

TEST(MyTest, AddTest3) {
    vector<int> v = {-1,5,3,4,0,6,-3};
    ListNode* input = build_linklist(v);
    Solution slu ;
    ListNode* res = slu.insertionSortList(input);
    print(res);

    EXPECT_EQ(res->val, -3);
}

int main(int argc, char *argv[]) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}
